package leetcode_1000;


//用 / \ 分割一个矩形 问最后这个大矩形有多少分离的面积块
//1：union find 合并规则
//2：数学问题 用点-边+联通量
//https://www.bilibili.com/video/av38512406
public class RegionsCutBySlashes_959 {
	class DSU {
	    int[] parent;
	    public DSU(int N) {
	        parent = new int[N];
	        for (int i = 0; i < N; ++i)
	            parent[i] = i;
	    }
	    public int find(int x) {
	        if (parent[x] != x) parent[x] = find(parent[x]);
	        return parent[x];
	    }
	    public void union(int x, int y) {
	        parent[find(x)] = find(y);
	    }
	}
	
	public int regionsBySlashes(String[] grid) {
        int N = grid.length;
        DSU dsu = new DSU(4 * N * N);
        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c) {
                int root = 4 * (r * N + c);
                char val = grid[r].charAt(c);
                if (val != '\\') {
                    dsu.union(root + 0, root + 1);
                    dsu.union(root + 2, root + 3);
                }
                if (val != '/') {
                    dsu.union(root + 0, root + 2);
                    dsu.union(root + 1, root + 3);
                }

                // north south
                if (r + 1 < N)
                    dsu.union(root + 3, (root + 4 * N) + 0);
                if (r - 1 >= 0)
                    dsu.union(root + 0, (root - 4 * N) + 3);
                // east west
                if (c + 1 < N)
                    dsu.union(root + 2, (root + 4) + 1);
                if (c - 1 >= 0)
                    dsu.union(root + 1, (root - 4) + 2);
            }

        int ans = 0;
        for (int x = 0; x < 4 * N * N; ++x) {
            if (dsu.find(x) == x)
                ans++;
        }

        return ans;
    }
}
